GATE CSE 2000
Q11.
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the following is always true?Q12.
Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right subtrees, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?Q13.
Let L denote the languages generated by the grammar S \to 0S0 \mid 00. Which of the following is TRUE?Q14.
Consider the following decision problems: (P1): Does a given finite state machine accept a given string? (P2): Does a given context free grammar generate an infinite number of strings? Which of the following statements is true?Q16.
Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statement is always true?Q18.
The number of tokens in the following C statement is printf("i=%d, &i=%x", i, &i);Q19.
Let G be an undirected connected graph with distinct edge weights. Let e_{max} be the edge with maximum weight and e_{min} the edge with minimum weight. Which of the following statements is false?Q20.
Given the following relation instance. \begin{array}{|l|l|l|}\hline \text{X} & \text{Y} & \text{Z} \\\hline \text{1} & \text{4} & \text{2} \\ \text{1} & \text{5} & \text{3} \\ \text{1} & \text{6} & \text{3} \\ \text{3} & \text{2} & \text{2} \\\hline \end{array}Which of the following functional dependencies are satisfied by the instance?